import java.util.HashMap;
import java.util.Stack;

/*
 * @lc app=leetcode.cn id=496 lang=java
 *
 * [496] 下一个更大元素 I
 */

// @lc code=start
// 最明显的做法就是暴力的每次都去扫描nums2，那这样效率会很低，复杂度log(n2)了
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> s = new Stack<Integer>();
        HashMap<Integer,Integer> h = new HashMap<Integer,Integer>();
// 注意我不知道是jdk版本的问题还是啥，我记得jdk8之后前面是不用写<integer,integer>的，因为后面写了前面就不用写了

        int[] result = new int[nums1.length];//先开一个数组

        for(int num : nums2){
            while( !s.isEmpty() && s.peek()<num ){//注意先判断不空，如果是空的peek可能出错
                h.put(s.pop(), num);//前面所有小于num的都得放进去
            }
            s.push(num);
        }
       

        for(int i =0 ;i<nums1.length;i++){
            result[i] = h.getOrDefault(nums1[i], -1);
            //这个getOrDefault如果Key找不到会自动把后面的defaultValue返回
        }
        return result;
    }
}
// @lc code=end

